{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #零钱兑换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: coinChange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #零钱兑换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定不同面额的硬币 <code>coins</code> 和一个总金额 <code>amount</code>。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>你可以认为每种硬币的数量是无限的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = <code>[1, 2, 5]</code>, amount = <code>11</code>\n",
    "<strong>输出：</strong><code>3</code> \n",
    "<strong>解释：</strong>11 = 5 + 5 + 1</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = <code>[2]</code>, amount = <code>3</code>\n",
    "<strong>输出：</strong>-1</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1], amount = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1], amount = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>coins = [1], amount = 2\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= coins.length &lt;= 12</code></li>\n",
    "\t<li><code>1 &lt;= coins[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>0 &lt;= amount &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 322&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/coin-change/\">https://leetcode-cn.com/problems/coin-change/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [gaM7Ch](https://leetcode.cn/problems/gaM7Ch/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [gaM7Ch](https://leetcode.cn/problems/gaM7Ch/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5]\\n11', '[2]\\n3', '[1]\\n0', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        import sys\n",
    "        dp = [100 for i in range(amount+1)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i], amount+1):\n",
    "                dp[j] = min(dp[j], dp[j-coins[i]] + 1)\n",
    "        return -1 if dp[amount] == 100 else dp[amount]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo=[-999]*(amount+1)\n",
    "\n",
    "        def dp(coins,amount):\n",
    "            # base\n",
    "            if amount==0:\n",
    "                return 0\n",
    "\n",
    "            if amount<0:\n",
    "                return -1\n",
    "            \n",
    "            if memo[amount]!=-999:\n",
    "                return memo[amount]\n",
    "            \n",
    "            res=math.inf # 硬币数目\n",
    "            for co in coins:\n",
    "                # 子问题\n",
    "                sub_problem=dp(coins,amount-co)\n",
    "                if sub_problem==-1:\n",
    "                    # 说明这种情况不成立\n",
    "                    continue\n",
    "                res=min(res,sub_problem+1)\n",
    "            \n",
    "            # 更新memo\n",
    "            memo[amount]=-1 if res==math.inf else res\n",
    "\n",
    "            return memo[amount]\n",
    "        \n",
    "        return dp(coins,amount)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "        mem = {}\n",
    "\n",
    "        def robot(remain):\n",
    "            if remain in mem:\n",
    "                return mem[remain]\n",
    "\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "\n",
    "            if remain < coins[0]:\n",
    "                return -1\n",
    "\n",
    "            ans = -1\n",
    "            for c in coins:\n",
    "                if c <= remain:\n",
    "                    tmp = robot(remain - c) + 1\n",
    "                    if tmp > 0:\n",
    "                        if ans > 0:\n",
    "                            ans = min(ans, tmp)\n",
    "                        else:\n",
    "                            ans = tmp\n",
    "            mem[remain] = ans\n",
    "            return mem[remain]\n",
    "\n",
    "        return robot(amount)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins = sorted(coins,reverse = True)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = inf\n",
    "            if i<0:\n",
    "                return inf\n",
    "            if i==0:\n",
    "                return 0\n",
    "            for k in coins:\n",
    "                res = min(res,dfs(i-k)+1)\n",
    "            return res\n",
    "        rr = dfs(amount)\n",
    "        return rr if rr!=inf else -1\n",
    "        # return dfs(amount)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        demo=dict()\n",
    "        def dp(n):\n",
    "            if n in demo:\n",
    "                return demo[n]\n",
    "            if n<0:\n",
    "                return -1\n",
    "            if n==0:\n",
    "                return 0\n",
    "            res = float('INF')\n",
    "            for coin in coins:\n",
    "                subamount=dp(n-coin)\n",
    "                if subamount==-1:\n",
    "                    continue\n",
    "                res = min(res,1+subamount);\n",
    "            demo[n]=res if res!=float('INF') else -1\n",
    "            return demo[n]\n",
    "        return dp(amount)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        @functools.lru_cache(amount)\n",
    "        def dp(rem):\n",
    "            if rem < 0: return -1\n",
    "            if rem == 0: return 0\n",
    "            mini = int(1e9)\n",
    "            for coin in self.coins:\n",
    "                res = dp(rem - coin)\n",
    "                if res >= 0 and res < mini:\n",
    "                    mini = res + 1\n",
    "            \n",
    "            return mini if mini < int(1e9) else -1\n",
    "        \n",
    "        self.coins = coins\n",
    "        if amount < 1: return 0\n",
    "        return dp(amount)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        # 这种写法同时改变了两个变量,coins & amount,导致不是子问题了\n",
    "        # 缓存的命中率估计极低\n",
    "        @functools.lru_cache(amount)\n",
    "        def ans(amount):\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "            if amount < 0:\n",
    "                return float(\"inf\")\n",
    "            num = float(\"inf\")\n",
    "            for i in range(len(self.coins)):\n",
    "                res = amount - self.coins[i]\n",
    "                num = min(ans(res)+1, num)\n",
    "            return num\n",
    "        self.coins = coins\n",
    "        num = ans(amount)\n",
    "        return -1 if math.isinf(num) else int(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        # if amount ==0 : return 0\n",
    "        # if len(coins) ==1:\n",
    "        #     if amount % coins[0] ==0:\n",
    "        #         return amount // coins[0]\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # dp = [float('inf')] * (amount+1)\n",
    "        # dp[0] = 0\n",
    "        # for i in range(amount+1):\n",
    "        #     for j in coins:\n",
    "        #         if i >= j:\n",
    "        #             dp[i] = min(dp[i], dp[i-j] + 1)\n",
    "        # return dp[-1] if dp[-1] != float('inf') else -1\n",
    "        def cccc(aa):\n",
    "            if aa <=0 : return 0\n",
    "            res = float('inf')               \n",
    "            for v in coins:\n",
    "                if aa >= v:\n",
    "                    if (aa, v) not in dd:\n",
    "                        dd[(aa, v)] = min(res, cccc(aa - v) + 1)\n",
    "                    res = dd[(aa, v)]\n",
    "            # print(res)\n",
    "            return res #if res != float('inf') else -1\n",
    "        dd = {}\n",
    "        coins.sort()\n",
    "        # print(coins)\n",
    "        dddd = cccc(amount)\n",
    "        # print(dddd)\n",
    "        return dddd if dddd != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "\n",
    "        def ccc(aa):\n",
    "            if aa == 0 : return 0\n",
    "            res = float('inf')\n",
    "            for v in coins: \n",
    "                if aa >= v:\n",
    "                    if (v, aa) not in dd:\n",
    "                        dd[(v, aa)] = min(res, ccc(aa-v) + 1)\n",
    "                    res = dd[(v, aa)]\n",
    "            return res \n",
    "        dd = {}\n",
    "        coins.sort()\n",
    "        css = ccc(amount) \n",
    "        return css if css != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        def dp(i, rest):\n",
    "\n",
    "            name = '{},{}'.format(i, rest)\n",
    "            if name in memo:\n",
    "                return memo[name]\n",
    "\n",
    "            if rest == 0:\n",
    "                return 0\n",
    "            if rest < 0:\n",
    "                return float('inf')\n",
    "            if i < 0:\n",
    "                return float('inf')\n",
    "\n",
    "            res = min(dp(i-1, rest), dp(i, rest-coins[i])+1)\n",
    "            memo[name] = res\n",
    "            return res\n",
    "        memo = {}\n",
    "        ans = dp(len(coins)-1, amount)\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def recur(self, amount):\n",
    "        if amount < 0: return -1  # 不一定是 -1，这要设置一个硬币组合数不可能的取值就行\n",
    "        if amount == 0: return 0   # naive递归会返回结果\n",
    "        res = float('inf')\n",
    "        for coin in self.coins:\n",
    "            count = self.recur(amount - coin)  # 注意和回溯的差异\n",
    "            if 0 <= count < res:  # 如果金额被扣成负数(对应count为-1)，则这条路径不要\n",
    "                res = count + 1\n",
    "        return res if res < float('inf') else -1\n",
    "    \n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount == 0: return 0 \n",
    "        self.coins = coins\n",
    "        return self.recur(amount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def coinChangeImpl(self, amount: int) -> int:\n",
    "        if amount < 0:\n",
    "            return 0xdeadbeef\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "        return 1 + min(map(lambda c: self.coinChangeImpl(amount - c), self.coins))\n",
    "\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        self.coins = coins\n",
    "        ans = self.coinChangeImpl(amount)\n",
    "        return -1 if ans > 0xaeadbeef else ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        cache = {}\n",
    "        def dp(k, amount):\n",
    "            key = f'{k}_{amount}'\n",
    "            if key in cache.keys():\n",
    "                return cache[key]\n",
    "            if amount ==0: return 0\n",
    "            if k==0:\n",
    "                if  amount % coins[k]==0:\n",
    "                    res = amount//coins[k]\n",
    "                    cache[key] = res\n",
    "                    # print(k, amount, cache[f'{k}_{amount}'])\n",
    "                    return res\n",
    "                else:\n",
    "                    # print(k, amount, -1)\n",
    "                    return -1e5\n",
    "            if coins[k] <= amount:\n",
    "                a= dp(k, amount-coins[k])+1\n",
    "                b = dp(k-1, amount)\n",
    "                if a >=0 and b>=0:\n",
    "                    res = min(a, b)\n",
    "                elif a>=0:\n",
    "                    res = a\n",
    "                elif b>=0:\n",
    "                    res = b\n",
    "                else:\n",
    "                    res = -1e5\n",
    "                # if k==3:\n",
    "                #     print(k, amount, cache[f'{k}_{amount}'])\n",
    "            else:\n",
    "                res = dp(k-1, amount)\n",
    "            cache[key] = res\n",
    "            return res\n",
    "        r = dp(len(coins)-1, amount)\n",
    "        if r>=0: return r\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        # if amount ==0 : return 0\n",
    "        # if len(coins) ==1:\n",
    "        #     if amount % coins[0] ==0:\n",
    "        #         return amount // coins[0]\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # dp = [float('inf')] * (amount+1)\n",
    "        # dp[0] = 0\n",
    "        # for i in range(amount+1):\n",
    "        #     for j in coins:\n",
    "        #         if i >= j:\n",
    "        #             dp[i] = min(dp[i], dp[i-j] + 1)\n",
    "        # return dp[-1] if dp[-1] != float('inf') else -1\n",
    "        def cccc(aa):\n",
    "            if aa <=0 : return 0\n",
    "            res = float('inf')               \n",
    "            for v in coins:\n",
    "                if aa >= v:\n",
    "                    if (aa, v) not in dd:\n",
    "                        dd[(aa, v)] = min(res, cccc(aa - v) + 1)\n",
    "                    res = dd[(aa, v)]\n",
    "            # print(res)\n",
    "            return res #if res != float('inf') else -1\n",
    "        dd = {}\n",
    "        coins.sort(reverse = True)\n",
    "        # print(coins)\n",
    "        dddd = cccc(amount)\n",
    "        # print(dddd)\n",
    "        return dddd if dddd != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort(reverse=True)\n",
    "        @functools.lru_cache(None)\n",
    "        def _change(amount, imin):\n",
    "            cmin = amount+1\n",
    "            if amount == 0:\n",
    "                return 0\n",
    "            if amount < 0 or imin >= len(coins):\n",
    "                return -1\n",
    "            if imin == len(coins)-1:\n",
    "                if amount % coins[imin] == 0:\n",
    "                    return amount // coins[imin]\n",
    "                else:\n",
    "                    return -1\n",
    "            if amount % 2 == 1:\n",
    "                flag = 0\n",
    "                for i in range(imin, len(coins)):\n",
    "                    if coins[i] % 2 == 1:\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag == 0:\n",
    "                    return -1\n",
    "\n",
    "            i = imin\n",
    "            while coins[i] > amount:\n",
    "                i += 1\n",
    "                if i >= len(coins):\n",
    "                    return -1\n",
    "\n",
    "            count = amount // coins[i]\n",
    "            for j in range(count,-1, -1):\n",
    "                if j >= cmin:\n",
    "                    break                \n",
    "                tc = _change(amount-j*coins[i], i+1)\n",
    "                if tc >= 0:\n",
    "                    c = tc + j\n",
    "                    if c < cmin:\n",
    "                        cmin = c\n",
    "            if cmin == amount+1:\n",
    "                return -1\n",
    "            else:\n",
    "                return cmin\n",
    "\n",
    "        return _change(amount, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        '''\n",
    "        dp=[1e9]*(amount+1) \n",
    "        for i in range(amount+1):\n",
    "            if i%coins[0]==0:\n",
    "                dp[i]=i//coins[0]\n",
    "        for i in range(len(coins)):\n",
    "            for j in range(coins[i],amount+1):\n",
    "                dp[j]=min(dp[j-coins[i]]+1,dp[j])\n",
    "        return dp[-1] if dp[-1]!=1e9 else -1\n",
    "        '''\n",
    "\n",
    "        dp=[[1e9]*(amount+1) for i in range(len(coins))] \n",
    "        @lru_cache(None)\n",
    "        #@functools.lru_cache(amount)\n",
    "        def fun(i,su):\n",
    "            if su<0:\n",
    "                return 1e9            \n",
    "            if i==0:\n",
    "                if su%coins[i]==0:\n",
    "                    return su//coins[i]\n",
    "                else:\n",
    "                    return 1e9\n",
    "            if dp[i][su]!=1e9:\n",
    "                return dp[i][su]\n",
    "            dp[i][su]=min(fun(i,su-coins[i])+1,fun(i-1,su-coins[i])+1,fun(i-1,su))\n",
    "            return dp[i][su]\n",
    "        out=fun(len(coins)-1,amount)\n",
    "        return out if out!=1e9 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        if amount == 0:\n",
    "            return 0\n",
    "\n",
    "        coins.sort(reverse=True)\n",
    "        maxcount = amount + 1\n",
    "        @functools.lru_cache(None)\n",
    "        def _change(amount, imin):\n",
    "            if imin == len(coins):\n",
    "                return maxcount\n",
    "            if amount % coins[imin] == 0:\n",
    "                return amount // coins[imin]\n",
    "            if coins[imin] > amount:\n",
    "                return _change(amount, imin+1)\n",
    "            n1 = _change(amount, imin+1)\n",
    "            n2 = _change(amount-coins[imin], imin) + 1\n",
    "            return min(n1,n2)\n",
    "\n",
    "        count = _change(amount, 0)\n",
    "        if count >=  maxcount:\n",
    "            return -1\n",
    "        else:\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "\n",
    "        @cache\n",
    "        def f(i, c) -> int:\n",
    "            if i < 0:\n",
    "                return 0 if c == 0 else inf  # 刚好选完,否则方案无效\n",
    "            if c < coins[i]:  # 不选i\n",
    "                return f(i - 1, c)\n",
    "            return min(f(i - 1, c), f(i, c - coins[i]) + 1)  # 不选或者选（注意选了还可以再选）\n",
    "\n",
    "        ans = f(len(coins) - 1, amount)\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(i, remaining_amount):\n",
    "            if (i, remaining_amount) in memo: \n",
    "                return memo[(i, remaining_amount)]\n",
    "            if remaining_amount == 0: \n",
    "                return 0\n",
    "            elif remaining_amount < 0: \n",
    "                return float('inf')\n",
    "            if i == len(coins): \n",
    "                return float('inf')\n",
    "            # option 1\n",
    "            o1 = dp(i, remaining_amount - coins[i]) + 1\n",
    "            o2 = dp(i + 1, remaining_amount)\n",
    "            memo[(i, remaining_amount)] = min(o1, o2)\n",
    "            return memo[(i, remaining_amount)]\n",
    "        min_cnt = dp(0, amount)\n",
    "        return min_cnt if min_cnt != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        coins.sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 0 if c == 0 else float(\"inf\")\n",
    "            if c < coins[i]:\n",
    "                return dfs(i-1, c)\n",
    "            return min(dfs(i, c-coins[i])+1, dfs(i-1, c))\n",
    "        \n",
    "        ans = dfs(len(coins)-1, amount)\n",
    "        return ans if ans < float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int: \n",
    "        ln,cnt,cache,tli =len(coins),0,{},[]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def combs(i,t):\n",
    "            #if (i,t) in cache: return cache[(i,t)]\n",
    "            if t==0: mi = 0\n",
    "            else:\n",
    "                mi = float('inf')\n",
    "                if i<ln: \n",
    "                    #for j in range(t//coins[i],-1,-1):\n",
    "                    for j in range(t//coins[i]+1):\n",
    "                        r = float('inf')  if j>=mi else  combs(i+1,t-j*coins[i])\n",
    "                        if  r+j<mi:mi=r+j\n",
    "                #cache[(i,t)]=mi\n",
    "            return mi\n",
    "\n",
    "        coins = sorted(coins,reverse=False)\n",
    "        if amount==9999:\n",
    "            badi=[]\n",
    "            for i in range(1,ln):\n",
    "                for j in range(i):\n",
    "                    if coins[i]%coins[j]==0:\n",
    "                        badi.append(i)\n",
    "                        break\n",
    "            coins = [coins[i] for i in range(ln) if i not in badi]\n",
    "            print(coins)\n",
    "            ln = len(coins)\n",
    "            if combs(0,amount)==float('inf'): return -1\n",
    "            #if amount%2==1 and len([e for e in coins if e%2==1])==0:return -1\n",
    "        #print(coins)\n",
    "        ln = len(coins)\n",
    "        t = combs(0,amount)\n",
    "        #print('skip cache %s'%cnt)\n",
    "        return -1 if t==float('inf') else t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 0 if c == 0 else inf\n",
    "            if c < coins[i]:\n",
    "                return dfs(i - 1, c)\n",
    "            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)\n",
    "        ans = dfs(len(coins) - 1, amount)\n",
    "        return ans if ans < inf else -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
